#include<bits/stdc++.h>
using namespace std;
int T,n,m,mod;
long long qmi(long long a,int b)
{
	long long res = 1;
	while(b)
	{
		if(b & 1) (res *= a) %= mod;
		(a *= a) %= mod;
		b >>= 1;
	}
	return res;
}
int ans[4000011];
int f[4000011],s[4000011];
long long ny,nny,nans;
vector<pair<int,int> > v[4000011];
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	freopen("pr.in","r",stdin);
	freopen("pr.out","w",stdout);
	cin >> mod;
	cin >> T;
	for(int i = 1;i <= T;i++)
	{
		cin >> n >> m;
		v[m].push_back({n,i});
	}
	for(m = 1;m <= 2000;m++) if(!v[m].empty())
	{
		sort(v[m].begin(),v[m].end());
		ny = qmi(m + 1,2 * mod - 4);
		nny = 1;
		int j = 0,mx = v[m][v[m].size() - 1].first;
		f[0] = 1,s[0] = 1;
		for(int i = 1;i <= mx * m;i++) f[i] = 0;
		for(int i = 1;i <= mx;i++)
		{
			(nny *= ny) %= mod;
			s[0] = f[0];
			for(int k = 1;k <= i * m;k++)
			{
				s[k] = s[k - 1] + f[k];
				if(s[k] >= mod) s[k] -= mod;
			}
			for(int k = 0;k <= i * m;k++)
			{
				f[k] = s[k];
				if(k > m)
				{
					f[k] = f[k] + mod - s[k - m - 1];
					if(f[k] >= mod) f[k] -= mod;
				}
			}
			if(i == v[m][j].first)
			{
				nans = 0;
				for(int k = 0;k <= i * m;k++) nans = (nans + (long long)f[k] * f[k]) % mod;
				(nans *= nny) %= mod;
				nans = (mod + 1 - nans) * (mod + 1) / 2 % mod;
				while(i == v[m][j].first && j < v[m].size())
				{
					ans[v[m][j].second] = nans;
					j++;
				}
			}
		}
	}
	for(int i = 1;i <= T;i++) cout << ans[i] << "\n";
	return 0;
}
